package com.leetcode.partition3;

import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/8/21 9:34
 */
public class LC236二叉树的最近公共祖先 {

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return postorder(root, p, q);
    }

    private static TreeNode postorder(TreeNode root, TreeNode p, TreeNode q) {
        //因为二叉树不是有序的，因此需要使用后序遍历回溯过程来搜索整个二叉树
        if (root == q || root == p || root == null) return root;
        TreeNode left = postorder(root.left, p, q);      //在左子树寻找p或q
        TreeNode right = postorder(root.right, p, q);    //在右子树寻找p或q
        if (left != null && right != null) return root;         //当前的根节点就是p和q的最近公共祖先
        if (left == null) return right;         //left为null，right不为null，说明p或q都不存在左子树，至少有一个在右子树
        return left;
    }
}
